The Rectilinear k%2DBends TSP.

Modelling Behaviour Requirements for Automatic Interpretation

NP%2Dcompleteness and FPT Results for Rectilinear Covering Problems.

Architecture for Hybrid Robotic Behavior.

Reduction rules deliver efficient FPT%2Dalgorithms for covering points with lines.

Practical protocol for Yao%27s millionaires problem enables secure multi%2Dparty computation of metrics and efficient privacy%2Dpreserving k%2DNN for large data sets.

Mutually Visible Agents in a Discrete Environment.

Mutually Visible Agents in a Discrete Environment.

The Privacy of k%2DNN Retrieval for Horizontal Partitioned Data %2D%2D New Methods and Applications.
I hereby certify that the work embodied in this thesis is the result of original research and has not been submitted for a higher degree at any other University or Institution. (Signed)
A New Efficient Privacy%2DPreserving Scalar Product Protocol.
I hereby certify that the work embodied in this thesis is the result of original research and has not been submitted for a higher degree at any other University or Institution. (Signed)
Privacy%2DPreserving k%2DNN for Small and Large Data Sets.
I hereby certify that the work embodied in this thesis is the result of original research and has not been submitted for a higher degree at any other University or Institution. (Signed)
Fast Private Association Rule Mining by A Protocol for Securely Sharing Distributed Data.

Feature extraction and gating techniques for ultrasonic shaft signal classification.
 
Computer Science 2006

Two New Techniques for Hiding Sensitive Itemsets and Their Empirical Evaluation.

Privacy Preserving DBSCAN for Vertically Partitioned Data.
I hereby certify that the work embodied in this thesis is the result of original research and has not been submitted for a higher degree at any other University or Institution. (Signed)
Privacy Preserving DBSCAN for Vertically Partitioned Data.
I hereby certify that the work embodied in this thesis is the result of original research and has not been submitted for a higher degree at any other University or Institution. (Signed)
Sanitization of Databases for Refined Privacy Trade%2DOffs.

The Undirected Feedback Vertex Set Problem Has a Poly%28k%29 Kernel.

Using Temporal Consistency to Improve Robot Localisation.



Fast Cluster Polygonization and its Applications in Data%2DRich Environments.

Computer Science 2005

FPT is P%2DTime Extremal Structure I.
  We describe a broad program of research in parameterized complexity, and hows this plays out for the MAX LEAF SPANNING TREE problem. 
Optimal Paths for Mutually Visible Agents.

Usability of Real%2DTime Unconstrained WWW%2DCo%2DBrowsing for Educational Settings.

Computer Science 2004
Excessive packet loss rates can dramatically decrease the audio quality perceived by users of Internet telephony applications. Recent results suggest that error control schemes using forward error correction (FEC) are good candidates for decreasing the impact of packet loss on audio quality. With FEC schemes, redundant information is transmitted along with the original information so that the lost original data can be recovered at least in part from the redundant information. Clearly, sending additional redundancy increases the probability of recovering lost packets, but it also increases the bandwidth requirements and thus the loss rate of the audio stream. This means that the FEC scheme must be coupled to a rate control scheme. Furthermore, the amount of redundant information used at any given point in time should also depend on the characteristics of the loss process at that time (it would make no sense to send much redundant information when the channel is loss free), on the end to...
Dogs or Robots %2D Why do Children See Them as Robotic Pets Rather Than Canine Machines%3F
In the not too distant future Intelligent Creatures (robots, smart devices, smart vehicles, smart buildings, etc) will share the everyday living environment of human beings. It is important then to analyze the attitudes humans are to adopt for interaction with morphologically di#erent devices, based on their appearance and behavior. In particular, these devices will become multi-modal interfaces, with computers or networks of computers, for a large and complex universe of applications. Our results show that children are quickly attached to the word `dog&#039; reflecting a conceptualization that robots that look like dogs (in particular SONY Aibo) are closer to living dogs than they are to other devices. By contrast, adults perceive Aibo as having stronger similarities to machines than to dogs (reflected by definitions of robot). Illustration of the characteristics structured in the definition of robot are insu#cient to convince children Aibo is closer to a machine than to a dog.
A Hybrid Classification Approach to Ultrasonic Shaft Signals.
Abstract. In many applications of machine learning a series of feature extraction approaches and a series of classifiers are explored in order to obtain a system with the highest accuracy possible. In the application we discussed here at least two feature extraction approaches have been explored (Fast Fourier Transform) and Discrete Wavelet Transform, and at least two approaches to build classifiers have also been explored (Artificial Neural Networks and Support Vector Machines). If one combination seems superior in terms of accuracy rate, shall we adopt it as the one to use or is there a combination of the approaches that results in some benefit? We show here how we have combined classifiers considering the misclassification cost to obtain a more informative classification for its application in the field.


Classification Ensembles for Shaft Test Data Empirical Evaluation.
 
Support Vector Machine Classification of Ultrasonic Shaft Inspection Data Using Discrete Wavelet Transform.
Abstract While many non-destructive ultrasonic signal test scenarios involve very shallow surfaces, signals for testing shafts are long and the new problem of mode-converted reflection emerges. They are echoes that do not correspond to cracks in the material, neither to characteristics of the shaft. Also, the length of the signals demands the application of efficient feature extraction mechanism to reduce the dimension of the pattern vectors and make classifier training feasible. The previous study by authors [9] established experimentally that Discrete Wavelet Transform (DWT) provided faster and more reliable feature extraction for Artificial Neural Networks (ANN) in these long signals in shafts. As an extended work, a new comparative experiment involving Support Vector Machines (SVM) approach instead of ANN models are made so that more confidence can be placed in the comparison result especially when there are only a limited number of training examples. The classification result from employing two different feature extraction schemes is also analyzed to investigate whether there exists any special relationship between feature types and class types. This investigation set the baseline for the future work of the authors, which is building a more advanced hybrid classifier model using multiple feature extraction schemes.
A Descriptive Language for Flexible and Robust Object Recognition.

Fast and Robust General Purpose Clustering Algorithms.
General purpose and highly applicable clustering methods are usually required during the early stages of knowledge discovery exercises. k-Means has been adopted as the prototype of iterative model-based clustering because of its speed, simplicity and capability to work within the format of very large databases. However, k-Means has several disadvantages derived from its statistical simplicity. We propose an algorithm that remains very efficient, generally applicable, multi-dimensional but is more robust to noise and outliers. We achieve this by using the discrete median rather than the mean as the estimator of the center of a cluster. Comparison with k-Means, Expectation Maximization and Gibbs sampling demonstrates the advantages of our algorithm.
Generating Nearly Sorted Sequences %2D The use of measures of disorder.

Cluster Validity Using Support Vector Machines.
Abstract- Gaining confidence that a clustering algorithm has produced meaningful results and not an accident of its usually heuristic optimization is central to data analysis. This is the issue of validity and we propose here a method by which Support Vector Machines are used to evaluate the separation in the clustering results. However, we not only obtain a method to compare clustering results from different algorithms or different runs of the same algorithm, but we can also filter noise and outliers. Thus, for a fixed data set we can identify what is the most robust and potentially meaningful clustering result. A set of experiments illustrates the steps of our approach.
Group unified histories an instrument for productive unconstrained co%2Dbrowsing.

Feature Extraction Techniques for Ultrasonic Shaft Signal Classification.
Abstract. Discrete Wavelet Transform (DWT) coefficients of ultrasonic test signals are considered useful features for input into classifiers due to their effective timefrequency representation of non-stationary signals. However, DWT exhibits a timevariance problem that has resulted in reservations for its wide acceptance. In this paper, a new technique to derive a preprocessing method for time-domain A-scans signal is presented. This techniques offer consistent extraction of a segment of the signal from long signals that occur in the Non Destructive Testing of shafts. We performed a comparison using artificial neural networks and evaluated classification performance of the classifier supplied with features generated by our method. We compared with other alternatives and report the results here. We established experimentally that DWT coefficients can be used as a feature extraction scheme more reliably by using our new preprocessing technique. 1
Tracking bees %2D a 3D%2C outdoor small object environment.

Improved Object Recognition %2D The RoboCup 4%2DLegged League.

Foundations of Unconstrained Collaborative Web Browsing with Awareness.
Research has focused significantly in enabling the Web (WWW) for Computer Supported Cooperative Work (CSCW). However, surfing, the most common use in the WEB, remains an individual, rather than group activity. Previous attempts to provide collaborative browsing capability constrain some users to the command of a selected user who controls the browsers of others. We adapt the technology of unconstrained distributed collaborative editors to develop unconstrained collaborative Web browsing. However, the effective collaboration is dependent on the awareness of context and group activity. We develop the history mechanisms for our solution to provide 4 types of awareness commonly discussed in the literature of CSCW. 1.
Cutting Up is Hard to Do the Parameterized Complexity of k%2DCut and Related Problems.

A Memetic Algorithm Guided by Quicksort for the Error%2DCorrecting Graph Isomorphism Problem.

Multi%2DLevel Clustering and its Visualization for Exploratory Spatial Analysis.

Clustering Web Visitors by Fast%2C Robust and Convergent Algorithms.

Why so many clustering algorithms a position paper.

Effective and Efficient Boundary%2Dbased Clustering for Three%2DDimensional Geoinformation Studies.

Fast Spatial Clustering with Different Metrics and in the Presence of Obstacles.
In many GIS settings, the Euclidean metric is not applicable as the model for distance between points. Other geometric models are needed in many practical scenarios, for which urban geography is a common example. Recently, Estivill-Castro and Lee [8] proposed an effective and efficient boundary-based clustering method overcoming drawbacks of traditional spatial clustering, but has a geometric focus. By factoring out the topological aspects of the method we obtain a generic boundary-based clustering that robustly generalizes for arbitrary Minkowski distances and is capable of handling obstacles. We illustrate this with the Manhattan distance and the Dominance distance. Experiments demonstrate that our method consistently finds various types of high-quality clusters within subquadratic time. 1.
Effective and Efficient Boundary%2Dbased Clustering for Three%2DDimensional Geoinformation Studies.

Criteria on Proximity Graphs for Boundary Extraction and Spatial Clustering.
2 1
Non%2Dcrisp Clustering by Fast%2C Convergent%2C and Robust Algorithms.

Data Structures for Minimization of Total Within%2DGroup Distance for Spatio%2Dtemporal Clustering.

Categorizing Visitors Dynamically by Fast and Robust Clustering of Access Logs.
Clustering is a fundamental task in data mining that plays a central role in segmenting markets. The identification of categories of visitors to a web site is very useful towards improved web design and improved web applications. However, the large volume involved in mining access logs and visitation paths, and the uncertainty to fully identify the visitor demands efficient clustering algorithms that are also resistant to noise and outliers. Also, dissimilarity between visitation paths involves sophisticated evaluation and results in large dimension of attribute-vectors. Apparently, clustering must be based on computation of dissimilarity matrix and thus, requires quadratic time on the number of visitation paths (plus time for their preprocessing and for dissimilarity computations). We present a randomized, iterative algorithm (a la Expectation Maximization or k-means) but based on discrete medoids. We prove that our algorithm converges and that has subquadratic complexity.
Robust Distance%2DBased Clustering with Applications to Spatial Data Mining.
In this paper, we present a method for clustering geo-referenced data suitable for applications in spatial data mining, based on the medoid method. The medoid method is related to k-Means, with the restriction that cluster representatives be chosen from among the data elements. Although the medoid method in general produces clusters of high quality, especially in the presence of noise, it is often criticized for the\Omega\Gamma n 2 ) time that it requires. Our method incorporates both proximity and density information to achieve highquality clusters in subquadratic time; it does not require that the user specify the number of clusters in advance. The time bound is achieved by means of a fast approximation to the medoid objective function, using Delaunay triangulations to store proximity information.
Computing and Combinatorics
. We give several examples where PVM was successfully  used as a tool for distributed computation of solutions of combinatorial  problems. Involved topics are the computation of the solution of multidimensional  subset sum problems which appear in the construction  of block designs, the construction and classification of finite solvable  groups up to isomorphism, and the computation of spin polynomials  that are generating functions of ribbon tableaux and which lead to  generalizations of Hall-Littlewood functions.  R&#039;esum&#039;e. Nous donnons plusieurs exemples pour lesquels nous avons  utilis&#039;e PVM comme outil de distribution de r&#039;esolution de probl`emes  combinatoires. Les sujets abord&#039;es sont la r&#039;esolution du probl`eme  du sac-`a-dos multi-dimensionnel qui apparait dans la construction  des &#034;block designs &#034;, la construction et la classification groupes finis  r&#039;esolubles `a isomorphismes pr`es, et le calcul des polynomes de spin qui  sont des fonctions g&#039;en&#039;eratrices de tableaux de rub...
AUTOCLUST  Automatic Clustering of Point%2DData Sets in the Presence of Obstacles.

Fast and Robust General Purpose Clustering Algorithms.
General purpose and highly applicable clustering methods are usually required during the early stages of knowledge discovery exercises. k-Means has been adopted as the prototype of iterative model-based clustering because of its speed, simplicity and capability to work within the format of very large databases. However, k-Means has several disadvantages derived from its statistical simplicity. We propose an algorithm that remains very efficient, generally applicable, multi-dimensional but is more robust to noise and outliers. We achieve this by using the discrete median rather than the mean as the estimator of the center of a cluster. Comparison with k-Means, Expectation Maximization and Gibbs sampling demonstrates the advantages of our algorithm.
Hybrid Genetic Algorithms Are Better for Spatial Clustering.
Iterative methods and genetic algorithms have been used separately to minimise the loss function of many representative-based clustering formulations. Neither of them alone seems to be significantly better. Moreover, the trade-off of effort vs quality slightly favours gradient descent. We present a unifying view for the three most popular loss functions: least sum of squares, its fuzzy version and the log likelihood function. We identify commonalties in gradient descent algorithms for the three loss functions and the evaluation of the loss function itself. We can then construct hybrids (genetic algorithms with a mutation operation that performs few gradient descent steps) for all three clustering approaches. We demonstrate that these hybrids are much efficient and effective (significantly render better performance as normalised by the number of function evaluations). Keywords. Evolutionary computation, knowledge discovery in databases, statistical approaches, clustering...
AUTOCLUST  Automatic Clustering of Point%2DData Sets in the Presence of Obstacles.

On the chromatic number of tree graphs.

Robust Clustering of Large Data Sets with Categorial Attributes.

Convex group clustering of large geo%2Dreferenced data sets.
Clustering partitions a data set S = fs1 ; : : : ; sng ae !  m  into groups of nearby points. Distance-based clustering uses optimisation criteria for defining the quality of the partition. Formulations using representatives (means or medians of groups) have received much more attention than minimisation of the total within group distance (TWGD). However, this non-representative approach has attractive properties while remaining distance-based. While representative approaches produce partitions with non-overlapping clusters, TWGD does not. We investigate the restriction of TWGD to producing convex-hull disjoint groups and show that this problem is NP-complete in the Euclidean case as soon as m  2. Nevertheless we provide efficient algorithms for solving it approximately.  Keywords: clustering, optimisation, computational geometry, problem complexity, data mining in spatial databases. 1 Introduction  Clustering is a fundamental task in data analysis since it identifies groups in heterog...
Data Swapping Balancing Privacy against Precision in Mining for Logic Rules.

Robust Clustering of Large Geo%2Dreferenced Data Sets.

Randomized K%2DDimensional Binary Search Trees.
This paper introduces randomized K-dimensional binary search trees (randomized  Kd-trees), a variant of K-dimensional binary trees. This data structure allows the efficient maintenance of multidimensional records for any sequence of insertions and deletions; and thus, is fully dynamic. We show that several types of associative queries are efficiently supported by randomized Kd-trees. In particular, a randomized Kd-tree with  n records answers exact match queries in expected O(log n) time. Partial match queries are answered in expected O(n  1\Gammaf (s=K)  ) time, when s out of K attributes are specified, with 0 ! f(s=K) ! 1 a real valued function of s=K). Nearest neighbor queries are answered on-line in expected O(log n) time. Our randomized algorithms guarantee that their expected time bounds hold irrespective of the order and number of insertions and deletions.  Keywords: Randomized Algorithms, Multidimensional Data Structures, Kd-trees,  Associative Queries, Multidimensional Diction...
Discovering Associations in Spatial Data %2D An Efficient Medoid Based Approach.

Hybrid Genetic Algorithm for Solving the p%2DMedian Problem.

Illumination of Orthogonal Polygons with Orthogonal Floodlights.

Cluster Discovery Techniques for Exploratory Spatial Data Analysis.


Collaborative Knowledge Acquisition with a Genetic Algorithm.
Inductive inference techniques that allow symbolic representation of the acquired knowledge facilitate knowledge validation, revision and understanding by human experts. EVOPROL v 1.1(EVOlutionary PROpositional Logic) is an inductive, efficient, versatile system for supervised learning of logic rules using a genetic algorithm. EVOPROL contributes to computer assisted knowledge acquisition because it allows discovery of flexible and/or alternative rules from examples. The approach presented here integrates sources of knowledge and establishes collaboration between the genetic searcher and the human expert.  1 Introduction  Building an expert system involves Knowledge Acquisition; that is, the process of eliciting, analyzing, and interpreting the knowledge that human experts use when solving problems and transforming this knowledge into a suitable machine representation. Experience has shown that this process is both difficult and time consuming and it is often a major bottleneck in the ...
Illumination with Orthogonal Floodlights.
) James Abello  1  , Vladimir Estivill-Castro  2  , Thomas Shermer  3  , Jorge Urrutia  4 1  Department of Computer Science, Texas A &amp; M University, College Station, Texas MS 3112, US. abello@cs.tamu.edu.  2  Laboratorio Nacional de Inform&#039;atica Avanzada, R&#039;ebsamen 80, Xalapa, Veracruz 91000, M&#039;exico. vlad@xalapa.lania.mx.  3  School of Computer Science, Simon Fraser University, Burnaby, B.C. V5A 1S6, Canada. shermer@cs.sfu.ca.  4  Department of Computer Science, University of Ottawa, Ottawa, Ontario K1N 6N5, Canada. jorge@csi.uottawa.ca. Abstract. We provide the first tight bound for covering a polygon with  n vertices and h holes with vertex guards. In particular, we provide tight bounds for the number of floodlights, placed at vertices or on the boundary, sufficient to illuminate the interior or the exterior of an orthogonal polygon with holes. Our results lead directly to simple linear, and thus optimal, algorithms for computing a covering of an orthogonal polygon. 1 Introduction  ...

Computer Science Research in Mexico.
this paper and for his comments. I am also grateful to Prof. Jo~ao Paulo Kitajima from the Universidade de Bras&#039;ilia who compiled some of the material used in this paper.  References
Illumination of Polygons with Vertex Lights.
We show that vertex floodlights of angle ß suffice to illuminate any polygon, and that no angle less than ß suffices for all polygons. A vertex floodlight of angle ff is an internal cone of light of aperture no more than ff with apex at a vertex. No vertex may have more than one floodlight.  Keywords: Computational geometry, visibility. 1 Introduction There has been recent interest in illumination by floodlights [1] [2] [6], a new variation on visibility problems in computational geometry. A floodlight of angle ff is a light that projects in a (contiguous) cone of angle at most ff. A floodlight placed in a simple polygon with its apex at a vertex, aimed entirely interior to the polygon, is called a vertex floodlight; if it has angle at most ff,  we will call it a vertex ff-light. We restrict each vertex to anchoring at most one floodlight. The question of illuminating a polygon with vertex floodlights was first explored in [3], in which it was established that every orthogonal polygon ...
Optimal Floodlight Illumination of Orthogonal Art Galleries.
We show that vertex floodlights of angle ß suffice to illuminate any polygon, and that no angle less than ß suffices for all polygons. 1 Introduction  There has been recent interest in illumination by floodlights [BGL  +  93] [CRCU93] [SS94], a new variation on visibility problems in computational geometry. A floodlight of angle ff is a light that projects in a cone of that angle. A floodlight placed in a simple polygon with its apex at a vertex is called a vertex floodlight; if it has angle ff, we will call it a vertex ff-light. The question of illuminating a polygon with vertex floodlights was first explored in [ECU94], in which it was established that every orthogonal polygon can be covered by b3(n \Gamma 1)=8c vertex ß=2-lights.  This work raised the question of what angle of vertex floodlights would suffice to cover any simple polygon. In [OX94] it was shown that vertex ß=2-lights do not suffice, even for monotone polygons. In this note we show that vertex ß-lights suffice, and no...
Foundations for Faster External Sorting %28Extended Abstract%29.

The Design of Competitive Algorithms via Genetic Algorithms.

Randomized Adative Sorting.

An Adaptive Generic Sorting Algorithm That Uses Variable Partitioning.
A sorting algorithm is adaptive if its run time for inputs of the same size n varies smoothly from O(n) to O(n log n) as the disorder of the input varies. It is well accepted that files that are already sorted are often sorted again and that many files occur naturally in nearly sorted state. Recently, researchers have focused their attention on sorting algorithms that are optimally adaptive with respect to several measures of disorder, (since the type of disorder in the input is unknown), and illustrating a need to develop tools for constructing adaptive algorithms for large classes of measures. We present a generic sorting algorithm that uses divide-and-conquer in which the number of subproblems depends on the disorder of the input and for which we can establish adaptivity with respect to an abstract measure. We present applications of this generic algorithm obtaining optimal adaptivity for several specific measures of disorder. Moreover, we define a randomized version of our generic ...
Right Invariant Metrics and Measures of Presortedness.

Randomized Adative Sorting.

Move%2Dto%2DEnd is Best for Double%2DLinked Lists.

Move%2Dto%2DEnd is Best for Double%2DLinked Lists.


A Survey of Adaptive Sorting Algorithms.
Introduction and Survey; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems --- Sorting and Searching; E.5 [Data]: Files --- Sorting/searching; G.3 [Mathematics  of Computing]: Probability and Statistics --- Probabilistic algorithms; E.2 [Data Storage Representation]: Composite structures, linked representations. General Terms: Algorithms, Theory. Additional Key Words and Phrases: Adaptive sorting algorithms, Comparison trees, Measures of disorder, Nearly sorted sequences, Randomized algorithms.  A Survey of Adaptive Sorting Algorithms 2 CONTENTS INTRODUCTION I.1 Optimal adaptivity I.2 Measures of disorder I.3 Organization of the paper 1.WORST-CASE ADAPTIVE (INTERNAL) SORTING ALGORITHMS 1.1 Generic Sort 1.2 Cook--Kim division 1.3 Partition Sort 1.4 Exponential Search 1.5 Adaptive Merging 2.EXPECTED-CASE ADAPTIV

Sorting%2C Measures of Disorder%2C and Worst%2DCase Performance.

Competitiveness and Response Time in On%2DLine Algorithms.

Sorting%2C Measures of Disorder%2C and Worst%2DCase Performance.

A New Measure of Presortedness

